package com.jeff.practice;

/**
 * 求两个字符串的最长公共子序列
 * 动态规划
 * 状态转移方程：
 * dp[i][j] = max(dp[i-1][j], dp[i][j-1], dp[i-1][j-1] + 1)
 * 解释：
 * 如果两个字符串的第i个字符相同，则最长公共子序列长度为上一行的第i-1个字符和第j-1个字符的长度之和+1；
 * 如果两个字符串的第i个字符不同，则最长公共子序列长度为上一行的第i-1个字符和第j个字符的长度和上一行的第i个字符和第j-1个字符的长度中的最大值；
 * 初始条件：
 * dp[0][j] = dp[i][0] = 0
 * 结果：
 * dp[m-1][n-1]即为两个字符串的最长公共子序列长度
 * 时间复杂度O(mn)
 * 空间复杂度O(mn)
 *
 * @author jeff
 */
public class LongestStringSubsequence {
    public static void main(String[] args) {
        int dynamicMethodResult = dynamicMethod("ABEGH", "AADFHR");
        System.out.println(dynamicMethodResult);
        int myMethodResult = myMethod("ABEGH", "AADFHR");
        System.out.println(myMethodResult);
    }

    /**
     * 动态规划法求两个字符串的最长公共子序列
     * 思路:
     * 定义dp[i][j]为s1的前i个字符和s2的前j个字符的最长公共子序列长度。
     * 状态转移方程:
     * 如果s1[i-1] == s2[j-1], 则dp[i][j] = dp[i-1][j-1] + 1;
     * 否则, dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
     * 初始条件:
     * dp[0][j] = dp[i][0] = 0;
     * 结果: dp[m-1][n-1]即为两个字符串的最长公共子序列长度。
     * 时间复杂度O(mn), 空间复杂度O(mn)
     *
     * @param s1 字符串1
     * @param s2 字符串2
     */
    private static int dynamicMethod(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();

        int[][] dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }

        }
        return dp[m][n];
    }

    /**
     * 基于子序列的定义,自己写的算法，思路:
     * 先比较s1和s2的长度，取较小值的首字母作为基准比较点，如果存在于另一个字符串中，则更新longest，并将该字符从字符串中删除,更新两个字符串的起始位置，然后继续比较；
     * 直到两个字符串有一方为空串，则返回longest。
     * 时间复杂度O(mn), 空间复杂度O(1)
     *
     * @param s1 字符串1
     * @param s2 字符串2
     */
    private static int myMethod(String s1, String s2) {
        int m = s1.length();
        int n = s2.length();
        int longest = 0;
       
        while (m > 0 && n > 0) {
            //比较m和n的大小，取较小值作为判断基准,辗转更新两个字符串的起始位置
            if (m < n) {
                char currentChar = s1.charAt(0);
                //判断当前字符是否在另一个字符串中
                int index = s2.indexOf(currentChar);
                if (index != -1) {
                    //如果在，则更新longest
                    longest = longest + 1;
                    //更新另一个起始位置
                    s2 = s2.substring(index + 1);

                }
                s1 = s1.substring(1);
            } else {
                char currentChar = s2.charAt(0);
                //判断当前字符是否在另一个字符串中
                int index = s1.indexOf(currentChar);
                if (index != -1) {
                    //如果在，则更新longest
                    longest = longest + 1;
                    //更新另一个起始位置
                    s1 = s1.substring(index + 1);

                }
                s2 = s2.substring(1);
            }
            m = s1.length();
            n = s2.length();
        }

        return longest;
    }
}

